回溯法（Backtracking）是一種暴力搜尋法，主要通過逐一嘗試所有可能的解來解決問題，並增加中止條件判斷來提前排除不可行的解，也可說是一種優化版的枚舉法。

在這個過程中，回溯法會將每種可能性列出，再透過遞迴來試探所有可能的解，遇到符合中止條件的選擇時，會停止繼續深入搜索，然後回退到上一個選擇點，嘗試其他選擇。

回溯法適合解決各類組合問題、切割問題、子集問題、排列問題（無需排序的組合問題）以及棋盤問題等。由於回溯法在解空間中逐層深入並探索所有可能性，因此它也可以視為深度優先搜尋法 (DFS) 的一種應用。

範例說明

• 問題：請列出所有由A、B、C組成的排列組合。
• 中止條件：當出現重複元素則停止深入列舉。
• 解法：我們使用回溯法來逐步生成排列。每次從未使用過的字母中選擇一個加入當前排列，直到排列的長度達到3。在生成排列的過程中，如果觸發中止條件，也就是當前的選擇會導致字母重複出現，就會停止深入列舉並回溯到上一步，嘗試其他可能的字母。重複這個過程直到列出所有可能。如下圖所示：

優點：

• 邏輯直觀易理解：回溯法試探所有可能的選擇，邏輯直觀，容易理解和實現。
• 適用範圍廣泛：可以解決多種問題，包括組合問題、排列問題、切割問題等。尤其適合解決那些需要考慮所有可能解的問題。
• 排除所有不可能解：回溯法能夠在其出現不可行解法時及時中止，以防深入造成時間浪費。

缺點：

• 時間複雜度高：在最壞情況下，回溯法需要遍歷所有可能的選擇，時間複雜度會很高，造成效率較低，不如預期。
• 僅適合解決小規模問題：雖然回溯法適用於許多類型的問題，但在處理非常大問題時，可能需要更高效的算法。

參考資料：

• 帶你學透回溯演算法（理論篇） - YouTube
• 演算法學習筆記：回溯法（Backtracking）& 分支定界法（Branch and Bound）- Medium
• [LeetCode 核心演算法] 回溯法（Backtracking）：最精簡解題技巧與必練題目 - secondlife